package main

import (
	"fmt"
)

func main() {
	nums := []int{5, 2, 3, 1}
	quickSort(nums)
	fmt.Println(nums)
}

// 快速排序
func quickSort(nums []int) []int {
	l := len(nums)
	if l == 0 || l == 1 {
		return nums //不需要排序
	}
	scopeSort(nums, 0, l-1)
	return nums
}

func scopeSort(list []int, from, to int) {
	if from >= to || from < 0 || to >= len(list) {
		return
	}

	base := list[from]
	left := from
	right := to
	for left < right {
		for list[right] >= base && left < right {
			right--
		}
		for list[left] <= base && left < right {
			left++
		}
		if left < right {
			list[left], list[right] = list[right], list[left] //swap
		}
	}
	list[from] = list[right]
	list[right] = base
	scopeSort(list, from, right-1)
	scopeSort(list, right+1, to)
}
